"""
1353. 最多可以参加的会议数目
尝试过
中等
相关标签
premium lock icon
相关企业
提示
给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。

你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。在任意一天 d 中只能参加一场会议。

请你返回你可以参加的 最大 会议数目。



示例 1：



输入：events = [[1,2],[2,3],[3,4]]
输出：3
解释：你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。
示例 2：

输入：events= [[1,2],[2,3],[3,4],[1,2]]
输出：4


提示：​​​​​​

1 <= events.length <= 105
events[i].length == 2
1 <= startDayi <= endDayi <= 105
"""
from heapq import heappop, heappush
from typing import List


class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        """
        做法，贪心，每次去找当前可学习的，left最小的课
        先排序，然后维护个最小堆，每天去找当当天的 最小堆
        :param events:
        :return:
        """
        max1 = max([e[1] for e in  events])
        dp = [ [] for _ in range(max1+1)]
        #left作为结点，加入到dp中，本质上已经排序了
        for event in events:
            dp[event[0]].append(event[1])
        h = [] #最小堆
        res = 0
        for index,item in enumerate(dp):
            #删除比当前left更小的，说明课已经结束了
            while h and h[0]<index:
                heappop(h)
            #把当前right加入
            for j in item:
                heappush(h,j)
            ##找left最小的课
            if h:
                res += 1
                heappop(h)
        return res


    def maxEvents_res1(self, events: List[List[int]]) -> int:
        mx = max(e[1] for e in events)

        # 按照开始时间分组
        groups = [[] for _ in range(mx + 1)]
        for e in events:
            groups[e[0]].append(e[1])

        ans = 0
        h = []
        for i, g in enumerate(groups):
            # 删除过期会议
            while h and h[0] < i:
                heappop(h)
            # 新增可以参加的会议
            for end_day in g:
                heappush(h, end_day)
            # 参加一个结束时间最早的会议
            if h:
                ans += 1
                heappop(h)
        return ans
if __name__ == '__main__':
    # print(Solution().maxEvents([[1,2],[2,3],[3,4]]))
    # print(Solution().maxEvents([[1,2],[2,3],[3,4],[1,2]]))
    print(Solution().maxEvents([[1,2],[2,3],[3,4],[1,2]]))